package algorithm.shortestpath;



import java.util.Vector;

public class SparseWeightedGraph <Weight extends Number & Comparable> implements WeightedGraph {
    /**顶点数*/
    private int n;
    /**边数*/
    private int m;
    /**是否为有向图*/
    private boolean directed;

    /**图的具体数据*/
    private Vector<Edge<Weight>>[] g;

    public SparseWeightedGraph(int n, boolean directed) {
        this.n = n;
        this.directed = directed;
        this.m=0;
        //g = new Vector<Edge<Weight>>[n];
         g = (Vector<Edge<Weight>>[])new Vector[n];
        for(int i=0;i<n;i++){
            g[i] = new Vector<Edge<Weight>>();
        }
    }

    /**返回定点数**/
    @Override
    public int V() {
        return n;
    }

    @Override
    public int E() {
        return m;
    }

    @Override
    public void addEdge(Edge e) {
        if(hasEdge(e.a(),e.b())){
            return;
        }
        g[e.a()].add(new Edge<>(e));

        if(e.a()!=e.b()&&!directed){
            g[e.b()].add(new Edge<>(e));
        }
     m++;
    }

    @Override
    public boolean hasEdge(int v, int w) {
        Vector<Edge<Weight>> vector = g[v];

        for(int i=0;i<vector.size();i++){
            if(vector.elementAt(i).b()==w){
                return  true;
            }
        }

        return  false;
    }

    @Override
    public void show() {

        for(int i=0;i<n;i++){
            System.out.println("vertex " + i + ":\t");
            for(int j=0;j<g[i].size();j++){
            Edge e = g[i].elementAt(j);
                System.out.println("( to"+e.getOther(i)+".wt:"+e.wt()+")\t");
            }
        }
    }

    @Override
    public Iterable<Edge<Weight>> adj(int v) {
        Vector<Edge<Weight>> vector = g[v];
        return vector;
    }

}
